【学习笔记】大指数的两种处理方法

2023-09-18 17:18| 来源: 网络整理| 查看: 265

问题背景

【描述】在这里插入图片描述【题目范围】我们可以看到，y 的数位最长达1e5+1 ！远远超过了任何一个数据类型的范围！那我们如何计算像这样的大指数呢？有两种解决方法，我们先学习第一种：算法——欧拉降幂。

对于算法欧拉降幂，你需要知道的东西有： 1、欧拉函数 ※※※ 2、快速幂对于欧拉函数的实现，我会分为两个部分去阐述。

首先给出核心公式

欧拉降幂公式

在这里插入图片描述其中，φ( c ) 表示欧拉函数的值，c 是模数。

欧拉函数的求解

【定义】欧拉函数：1~N中与N互质的数的个数

其计算公式为在这里插入图片描述其中，p 表示 n 的质因数。

【证明】点我看证明（视频）

【欧拉函数代码】

即实现上述公式

ll EulerFcuntion(ll p) //欧拉函数 { ll EulerNumber=p; for(ll i=2;i //如果是质因数 EulerNumber=EulerNumber/i*(i-1); //欧拉公式计算 while(p%i==0) p/=i; //除去相同质因数 } } if(p>1) EulerNumber=EulerNumber/p*(p-1); //最后一个质因数 return EulerNumber; }

【可能问题解释】

1、外层 for 循环是什么意思？

for(ll i=2;i ll EulerNumber=EulerFcuntion(p); //得到φ(c) ll len=strlen(y); ll DescendingPower=0; for(ll i=0;i ll result=1; while(power>0){ if(power&1) result=result*base%mod; power>>=1; base=(base%mod)*(base%mod); //底数平方 } return result; } ll EulerFcuntion(ll p) //欧拉函数 { ll EulerNumber=p; for(ll i=2;i EulerNumber=EulerNumber/i*(i-1); while(p%i==0) p/=i; } } if(p>1) EulerNumber=EulerNumber/p*(p-1); //最后一个质因数 return EulerNumber; } ll EulerDropPower(ll x,char y[],ll p) { ll EulerNumber=EulerFcuntion(p); //得到φ(p) ll len=strlen(y); ll DescendingPower=0; for(ll i=0;i int t; scanf("%d",&t); while(t--){ ll x,p; scanf("%lld%s%lld",&x,y,&p); ll ans=EulerDropPower(x,y,p); printf("%lld\n",ans); } return 0; }

现在介绍第二种处理方法（虽然是我自己取的名字）——数学模拟

【推导】在这里插入图片描述对于上面的推导式你可能看不懂，不要纠结，继续往下看。如下图。

（解释水平有限，没看懂可以私信我~ ）

AC代码 2 #include #include using namespace std; typedef long long ll; int main() { int t; scanf("%d",&t); while(t--){ ll x; string y; ll p; ll ans=1; cin>>x>>y>>p; for(int i=y.size()-1;i>=0;i--){ int t=y[i]-'0'; for(int j=1;j

【本文地址】

公司简介

联系我们